import java.util.List;

public class Solution {
    public static void main(String[] args) {
        /**
         * 解决递归经典问题：
         *  1，求斐波那契数列的第N项
         *  2，求解汉诺塔问题
         *  3，青蛙跳台阶问题*/
        Solution s = new Solution();

        // 1，求斐波那契数列的第N项
        System.out.println(s.fib(100));
    }

    public int fib1(int n) {
        /**
         * 求解第N项斐波那契数列
         * 从第0项开始
         *  解法：递归求通解
         *  缺陷：递归次数太多，此类题目还是使用迭代的方法更加合适*/
        // 1 递归出口
        if(n == 0) {
            return 0;
        }
        if(n == 1) {
            return 1;
        }

        // 2 递归主体
        return (fib1(n - 1) + fib1(n - 2)) % 1000000007;
    }

    public int fib(int n) {
        /**
         * 求解第N项斐波那契数列
         * 从第0项开始
         *  解法：使用动规方式求解
         * 状态表示：
         *  dp[i]表示第i项斐波那契数列值
         * 状态转移方程：
         *  dp[i] = dp[i-1] + dp[i-2];
         * 初始化：
         *  填写初始值
         *  */
        // 1 预处理
        int[] dp = new int[n+1];
        // -边界情况处理
        if(n == 0) {
            return 0;
        }
        if(n == 1) {
            return 1;
        }

        // 2 初始化
        dp[1] = 1;

        // 3 填表
        for(int i = 2; i <= n; i++) {
            dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
        }

        // 4 返回值
        return dp[n];
    }

    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        /**
         * 汉诺塔问题
         * 解法：
         *  使用递归求解
         * 问题：
         *  总是栈溢出，是否必须要添加个数？*/
        move(A.size(), A, B, C);
    }

    private static void move(int n, List<Integer> A, List<Integer> B, List<Integer> C) {
        /**
         * 需要传递待移动盘子的数量*/
        // 1 递归出口
        if(n <= 0) {
            return;
        }

        // 2 解决重复子问题
        // -step1
        move(n-1, A, C, B);
        // -step2
        C.add(A.remove(A.size()-1));
        // -step3
        move(n-1, B, A, C);
    }
}
